| class DIGRAPH_ALG{NTP, GTP < $RO_DIGRAPH{NTP}} |
|---|
| **** | NTP is the node index type and GTP is the graph type
__ A collection of some very simple graph traversal algorithms _ All the following routines assume that the graph is acyclic. They may go into an infinite loop or fail in some other way if the graph contains cycles. Usage: _____g:_DIGRAPH{INT}_:=_#; _____n1_::=_g.add_node(1); _____n2_::=_g.add_node(2); _____n3_::=_g.add_node(3) _____g.connect(n1,n2);_g.connect(n1,n3); _____Constructs: ______1 ______/\ _____2__3 _____Getting_the_layers_of_the_graph: ________l:_LIST{SET{INT}}_:=_#; ________loop_s:_SET{INT}_:=_DIGRAPH_ALG::layer!(g); _____________l_:=_l.append(s); _________end; |
| DIGRAPH_ALG{_} |
| is_topo_order(g: GTP,nodes: $ARR{NTP}): BOOL |
|---|
| **** | Verify that the nodes in "node_order" are in topological order, that each node's order is greater than the order of any of its parents. Better methods probably exist... |
| bf!(once g: GTP,once n: NTP): NTP |
|---|
| **** | Return all nodes reachable from "n" in breadth first order With inout arguments, also return the depth of the node |
| df!(once g: GTP,once n: NTP): NTP |
|---|
| **** | Return all nodes reachable from "n" in depth first order |
| layer!(once g: GTP): SET{NTP} |
|---|
| **** | Return the "layers" of the graph, i.e. peel off successive root sets Current indegree holds the current number of incoming per node When the number of incoming goes to zero, the node is visited and the current indegree values of all its outgoing are decremented. All nodes/edges start out live. Loop, at each iteration:
____Find_the_nodes_that_have_no_live_incoming_edges_and__yield_them ____Mark_the_nodes_and_all_edges_going_out_of_them_as_dead Until no more nodes are left alive |
| sink!(once g: GTP): NTP |
|---|
| **** | Yield all sink nodes in the graph "g" |
| source!(once g: GTP): NTP |
|---|
| **** | Yield all source nodes in the graph "g" |
| topo_order!(once g: GTP): NTP |
|---|
| **** | Yield nodes in topological order |